User blog:DontDrinkH20/H-Boogol-Boogol: Hopefully a very big non-salad number
WARNING!!! You should be well-equipped with model theoretic terminology and computability theoretic terminology before you work with this paper, as well as some basic set theory. To further complicate things, instead of working in ZFC, I'm working in GBC (or NBG as sometimes known)! Feel free to grab a notebook and take some notes as you go along. You might need them; this one is a real doozy. = What led up to this = There was originally going to be another subclass of Type C called the representable googolisms. These would be a weakening of the expressible googolisms where "metamathematical" was replaced by a less expressive type of language. However, I then realized that there was no known concise definition of "a natural number can be expressed by a language" so I decided to make one. It turns out that it doesn't require just a language, but rather a structure (which by definition is equipped with a language). From this point on, I assume that the reader understands the basics of model theory, which are required to understand how this is actually defined. So, I returned to defining the representable googolisms. However, I eventually realized that there were no known valid unrepresentable googolisms; so the class of current representable googolisms would be equal to the class of expressible googolisms. Because of this, I've now changed my mind of what I intend to do, and so instead of defining representable googolisms, I'm defining what might be (fingers crossed) the new largest valid googolism. I call this number H-Boogol-Boogol (although PLEASE come up with a better name if this works; this name kinda sucks). = A Buttload of Definitions = Here's a buttload of definitions leading up to the definition of H-Boogol-Boogol. Model Theoretic Logic The model theoretic logic \(\mathcal{L}^n(\{c_0,c_1...\},\{r_0,r_1...\},\{f_0,f_1...\})\) is the \(\mathcal{L}^n_{\omega,\omega}\)-logic (n-th order finitary logic) consisting of constant symbols \(c_0,c_1...\), relation symbols \(r_0,r_1...\), and function symbols \(f_0,f_1...\). I hope this counts as well-defined for most of you. NOTE: I am using standard semantics (not Henkin) meaning that within a structure \(\mathcal{M}\), n-th order quantification is over \(\mathcal{P}_{n-1}(M)\). The model theoretic logic (this is my definition, so don't look it up) \(\mathcal{L}^{<\omega}(\{c_0,c_1...\},\{r_0,r_1...\},\{f_0,f_1...\})\) is slightly different; it allows for \(n\)-th order quantification for any \(n\), but instead of using individual symbols for each type of quantification, \(n\)-th order quantification is signified by \(n\)-many symbols "\(Q\)" after the type of quantification, allowing for a finite set of symbols. A theory whose language is a model theoretic logic is called a model theory. Interpreting Arithmetic (Feferman def. generalized) *A model theory \(T\) interprets arithmetic iff: **There are formulae \(\varphi_+\), \(\varphi_{\cdot}\), \(\varphi_{S}\), and \(\varphi_0\) in the language of \(T\) such that for any model \(\mathcal{M}\models T\), there exists some substructure \(\mathcal{N}\) of \(\mathcal{M}\) and functions \(p:(N\times N)\rightarrow N\), \(m:(N\times N)\rightarrow N\), and \(S:N\rightarrow N\) such that: ***For any \(a,b,c\in N\), \(p(a,b)=c\Leftrightarrow\mathcal{N}\models\varphi_+(a,b,c)\) ***For any \(a,b,c\in N\), \(m(a,b)=c\Leftrightarrow\mathcal{N}\models\varphi_{\cdot}(a,b,c)\) ***For any \(a,b\in N\), \(S(a)=b\Leftrightarrow\mathcal{N}\models\varphi_{S}(a,b)\) ***There exists exactly one \(x\in N\) such that \(\mathcal{N}\models \varphi_0(x)\) ***The structure \(\mathcal{K}=(N;x,=,p,m,S)\) in the language of PA is a model of Peano arithmetic \(\mathcal{K}\) is then called an interpreting substructure of \(\mathcal{N}\). Intuitively, this is where \(T\) has natural-number-like objects in every model (if the language is first-order, then \(T\) proves the existence of natural-number-like objects). Standardization Formulas Corresponding Objects Then, given some number \(x\) in a standard model \(\mathcal{N}\), the standardization formula of \(x\) is simply \(\Sigma_x(v_0)\Leftrightarrow v_0=SSSS...(0)\) where there are \(x\)-many symbols "\(S\)". Then, (for any model \(\mathcal{K}\) of PA) the corresponding object of x in \(\mathcal{K}\) is the only object in \(\mathcal{K}\) which is defined by \(\Sigma_x\). Such exists because every model of PA, including \(\mathcal{K}\), is an extension of a standard model of PA (Skolem said it not me). Note that for any standard model \(\mathcal{N}\) of PA, every \(x\in N\) has a unique corresponding object in \(\mathcal{K}\). Therefore, for every object \(X\) of \(\mathcal{K}\), there is at most one \(x\in N\) such that the corresponding object of \(x\) in \(\mathcal{K}\) is \(X\). Computation on Theories Let the minimum language of a theory \(T\), \(\mathcal{L}(T)\) be the set of all distinct (nonequal) symbols that are used in \(T\) (it does not need to be the language of a model theoretic logic). Then let \(\text{GN}(T)\) be the set of all Gödel numberings of \(\mathcal{L}(T)\) if \(\mathcal{L}(T)\) is finite, and \(\text{GN}(l)\) be the set of all Gödel numberings of some finite language \(l\). I define a Gödel numbering as any bijection \(g:\mathcal{L}(T)\rightarrow|\mathcal{L}(T)|\) and then define \(\ulcorner\varphi\urcorner\) to be the Gödel number of \(\varphi\) with a given contextual Gödel numbering. Mu and Sigma If \(\mathcal{L}(T)\) is finite and \(T\) recursive and \(g\in\text{GN}(T)\) then \(\mu_g(T)\) is the least \(x\) such that there is an \(x\)-state DTM which, when given input \(n\), outputs \(\ulcorner\varphi_n\urcorner\) where \(\varphi_x\) enumerates \(T\) by Gödel number. By proof 1, \(\{T : \mu_g(T)\leq x\}\) is finite. Then let \(\mu(T)\) be '''\(\max\{\mu_g(T):g\in\text{GN}(T)\}\). Note that because \(\mathcal{L}(T)\) is finite, there are only finitely many Gödel numberings of \(\mathcal{L}(T)\), and therefore this set is finite and its maximum exists. By proof 2, \(\{T:\mu(T)\leq x\land\mathcal{L}(T)=l\}\) is finite. Given \(g\), if \(m\) is a DTM, then there is at most one \(T\) such that when given input \(n\), \(m\) outputs \(\ulcorner \varphi_n\urcorner\) where \(\varphi_x\) enumerates \(T\) by Gödel number. '''Let this \(T\) be \(\sigma_g(m)\). Note that: #\(\mu_g(T)\leq x\) if and only if there exists some \(x\)-state DTM \(m\) such that \(\sigma_g(m)=T\). #The set of all \(x\)-state DTMs \(m\) such that \(\sigma_g(m)\) exists is equinumerous to the set of all \(\sigma_g(m)\) for \(x\)-state DTMs \(m\) The Set of "Mother Symbols" Because any symbol in a language could be replaced with a symbol not in that language and the language would have the same properties, I'm going to define some non-rigorous (oh no!) sets of symbols. Let \(\mathbb{L}_f\), \(\mathbb{L}_c\), and \(\mathbb{L}_p\), be 3 disjoint sets of \(\aleph_0\)-many symbols each. Without loss of generality, it's also easy to show that model theoretic logics with the same NUMBER of constant symbols, function symbols, and relation symbols, have the same properties. As a result, I can enumerate each element of each set with \(f_0, f_1...\), \(c_0, c_1...\), and \(r_0, r_1...\) and then call \(\mathbb{L}^{<\omega}(x,y,z)\) the set of all logics which use \(f_0...f_a\) where \(a\leq x\), \(c_0...c_b\) where \(b\leq y\), and \(r_0...r_d\) where \(d\leq z\). Note that there are finitely many logics in \(\mathbb{L}^{<\omega}(x,y,z)\), but every \(<\omega\)-order model theoretic logic is equivalent to some logic in \(\mathbb{L}^{<\omega}(x,y,z)\) for some \(x,y,z\). This is why we don't lose any generality. Finally, let \(\mathfrak{L}^{<\omega}\) be the set of all logics \(l\) such that there are some \(x,y,z\) with \(l\in\mathbb{L}^{<\omega}(x,y,z)\). Just Before H-Boogol-Boogol We're getting pretty close to the end now. Just hang in there! Defining Pairs Let \(T\) be any model theory such that either: *\(T\) is satisfiable *There exists some function \(f\) which brings symbols of \(T\) to symbols \(f_0,f_1...\), \(r_0,r_1...\), \(c_0,c_1....\) such that \(V;C_0,C_1...,F_0,F_1...,R_0,R_1...)\) is a model of \(T\) for some sets \(C_0,C_1...\), functions \(F_0,F_1...\) and predicates \(R_0,R_1...\) \(T\) is then called semisatisfiable. If \(T\) meets the second condition at all (regardless of satisfiability), it is called verifiable with \((V;C_0,C_1...,F_0,F_1...,R_0,R_1...)\). Then, letting \(\varphi\) be some \(l\)-formula and letting \(x\in N\) where \(\mathcal{N}\) is a standard model of PA, \((T,\varphi)\) is a defining pair of \(x\) through \(\mathcal{N}\) iff: Then, letting \(\varphi\) be some \(l\)-formula and letting \(x\in N\) where \(\mathcal{N}\) is a standard model of PA, \((T,\varphi)\) is a defining pair of \(x\) through \(\mathcal{N}\) iff: *\(T\) is verifiable with \((V;C_0,C_1...,F_0,F_1...,R_0,R_1...)\) and: **\(T\) interprets arithmetic **\(\varphi\) defines exactly one set \(X\) which is an element of \(\omega\) which is the corresponding object of \(x\) in \((\omega;\in)\). *Or: **\(T\) interprets arithmetic **For any model \(\mathcal{M}\) of \(T\), there is an interpreting substructure \(\mathcal{K}\) of \(\mathcal{M}\) such that \(\varphi^{\mathcal{M}}\) defines exactly one object \(X\) which is an element of \(K\) such that: ***\(X\) is the corresponding object of \(x\) in \(\mathcal{K}\) (remember that at most one exists) REALLY Important is to note that for every such \(T\) and \(\varphi\), because \(\varphi\) is a defining formula, there is no other \(y\in N\) such that \((T,\varphi)\) is a defining pair of \(y\) through \(N\). Intuitively, \(\varphi\) defines the most \(x\)-like natural-number-ish object that \(T\) proves to exist. If \(T\) is REALLY REALLY POWERFUL, then \(\varphi\) is likely to be powerful as well, and \(\varphi\) can define a lot of natural numbers that perhaps PA cannot define. This is the way to use \(\varphi\) to define some natural number. (a,b)-representable objects (and a little proof) Letting \(\mathcal{N}\) be a standard model of PA and \(x\) be an element of \(N\), \(x\) is \((a,b)\)-representable in \(\mathcal{N}\) if and only if: *There are some FINITE \(F\subset\mathbb{L}_f\), \(C\subset\mathbb{L}_c\) and \(P\subset\mathbb{L}_p\) such that: **Letting \(l\) be \(\mathcal{L}^{<\omega}(C,P,F)\), there is some semisatisfiable \(l\)-theory \(T\) with \(\mu(T)\leq a\) and some \(l\)-formula \(\varphi\) of at most \(b\) symbols such that \((T,\varphi)\) is a defining pair of \(x\) through \(\mathcal{N}\). Each \((T,l)\) is a defining pair of AT MOST ONE number \(x\in\mathcal{N}\). We also know: *By proof 3, there are finitely many \(T\) with a language in \(\mathfrak{L}^{<\omega}\) such that \(\mu(T)\leq a\). *There are finitely many formulae of size at most \(b\) of language \(\mathcal{L}(T)\) because \(\mathcal{L}(T)\) is a model theoretic logic and therefore has finitely many symbols. *The set of all pairs of \(T\) with a language in \(\mathfrak{L}^n(\mathbb{L}_c,\mathbb{L}_p,\mathbb{L}_f)\) such that \(\mu(T)\leq a\) and of \(\varphi\) of language \(T\) is therefore finite, albeit probably very very large. *Since every such pair gets AT MOST ONE number \((a,b)\)-representable in \(\mathcal{N}\), but every \((a,b)\)-representable number gets AT LEAST ONE such pair, the set of all these pairs must be at least the size of the set of all \((a,b)\)-representable numbers in \(\mathcal{N}\). *Since the set of all \((a,b)\)-representable numbers in \(\mathcal{N}\) is bounded by the set of all such pairs, and the set of all such pairs is finite, we can deduce that the set of all \((a,b)\)-representable numbers in \(\mathcal{N}\) is finite. *'There are finitely many \((a,b)\)-representable numbers in \(\mathcal{N}\) for every standard model \(\mathcal{N}\) and every \(a\) and \(b\).' Intuitively, \(x\) is \((a,b)\)-representable when there is a formula of length at most \(b\) in a model theoretic logic in a system of mathematics which can be made easily with an \(a\)-state DTM. The H functions (where I define the number) Let \(x\) be the \(<^{\mathcal{N}}\)-maximal element of the set of all \((a,b)\)-representable numbers in \(\mathcal{N}\). Such exists because there are only finitely many. Then, \(\mathcal{H}_a\)-\(\text{Pre}_{\mathcal{N}}(b)\) is \(S^{\mathcal{N}}(x)\). That is, the smallest number larger than every \((a,b)\)-representable number in \(\mathcal{N}\). Then let \(\mathcal{H}_a(b)\) be the corresponding object of \(\mathcal{H}_a\)-\(\text{Pre}_{\mathcal{N}}(b)\) in \((\omega;\in)\). FINALLY, let \(\mathfrak{H}_a(b)\) be the largest number \(k\) such that for any inner model \(\mathcal{M}\) of ZFC, \(\mathcal{H}_a^{\mathcal{M}}(b)\) can be described in at least \(k\)-many successor functions. (This new definition is thanks to Emlightened, who showed me that forcing could be used to make a number which can be arbitrarily large in number of successor functions needed to describe it.) My number is \(\mathfrak{H}_{10\uparrow^{100}10}(10\uparrow^{100}10)\). That's why I call it H-boogol-boogol. By proof 4, H-boogol-boogol is larger than Rayo's number. Intuitively, \(\mathfrak{H}_a(b)\) is the smallest number larger than EVERY number which can be described with a system of mathematics that takes \(a\)-many states in a DTM to calculate and a formula in the language of that system in at most \(b\)-many symbols. = Proofs = Here I'm going to put all the proofs, so if you just want the definition you don't have to scroll a bunch. I refer to these proofs in order, so I call the first one Proof 1, the second one Proof 2, etc. Proof 1 Here's the first proof, the proof that given some finite set of symbols \(l\), a Gödel numbering \(g\) of \(l\), and a natnumb \(x\), \(\{T : \mu_g(T)\leq x\}\) is finite: #\(\{m:m\text{ is an }x-\text{state DTM}\}\) is finite (this is well-known) #\(|\{m:m\text{ is an }x-\text{state DTM and }\sigma_g(m)\text{ exists}\}|\) \(\leq|\{m:m\text{ is an }x-\text{state DTM}\}|=(4x+1)^{2x}\) #\(|\{\sigma_g(m):m\text{ is an }x-\text{state DTM and }\sigma_g(m)\text{ exists}\}|\leq(4x+1)^{2x}\) #\(|\{T:\exists m(m\text{ is an }x-\text{state DTM and }\sigma_g(m)=T)\}|\leq(4x+1)^{2x}\) #\(|\{T:\mu_g(T)\leq x\}|\leq(4x+1)^{2x}\) Proof 2 Now, given that, I'll prove that given some finite set of symbols \(l\) and a natnumb \(x\), \(\{T:\mu(T)\leq x\land\mathcal{L}(T)=l\}\) is finite: #For any Gödel numbering \(g\) of \(l\), \(\{T:\mu_g(T)\leq x\}\) is finite by Proof 1 #There are finitely many Gödel numberings of \(l\), therefore the set \(\bigcup_{g\in\text{GN}(l)}\{T:\mu_g(T)\leq x\}\) is finite #For every \(l\)-theory \(T\) such that \(\mu(T)\leq x\), there is some Gödel numbering \(g\) of \(l\) such that \(\mu_g(T)\leq x\), and therefore that \(T\) is in the set \(\bigcup_{g\in\text{GN}(l)}\{T:\mu_g(T)\leq x\}\), which is finite #Therefore, the set of all \(l\)-theories \(T\) such that \(\mu(T)\leq x\) is finite #\(\{T:\mu(T)\leq x\land\mathcal{L}(T)=l\}\) is finite (and it's size is at most \((4x+1)^{2x}\cdot(|l|!)\), that's your challenge to prove if you want because it's inconsequential here) Proof 3 Here I'll prove that there are finitely many \(T\) with a language in \(\mathfrak{L}^{<\omega}\) such that \(\mu(T)\leq x\) given some \(x\). The set of all \(\leq x\)-state DTMs is finite. Assume that there are infinitely many \(T\) with language \(l_{a,b,c}\in\mathbb{L}^{<\omega}(x,y,z)\) with \(\mu(T)\leq x\). Then, there is some DTM \(\mathfrak{M}\) which encodes infinitely many theories. An \(l_{a_0,b_0,c_0}\)-theory \(T_0\) and a \(l_{a_1,b_1,c_1}\)-theory \(T_1\) are encoded by the same DTM \(m\) if and only if there are some \(g_0,g_1\in\text{GN}(T)\) such that, when given input \(n\), \(m\) gives output \(\#_{g_0}\varphi_n=\#_{g_1}\psi_n\) where \(\varphi_n\) and \(\psi_n\) respectively order \(T_0\) and \(T_1\) by \(g_0\) and \(g_1\). This is only true if and only if the theories, as sets of strings, are roughly equivalent. That is to say, there is some function \(f\) which bijectively maps symbols from \(\mathcal{L}(T_0)\) to \(\mathcal{L}(T_1)\) such that \(F(abcdef...)=f(a)f(b)f©...\) is a bijection from \(T_0\) to \(T_1\). This problem is trivial and left as an exercise for the reader. How many \(l\)-theories \(T_0,T_1...\) can there exist which are all bijective in this way? Well, it turns out that it is finite, meaning a contradiction has been reached (meaning that there are finitely many \(T\) with a language in \(\mathfrak{L}^{<\omega}\) such that \(\mu(T)\leq x\)). Here's why: #Let \(T_0,T_1...\) be a countably infinite sequence of \(l\)-theories \(T\) such that for any \(n\) and \(m\), there is some function \(f\) which bijectively maps symbols from \(l\) to itself such that \(F(abcdef...)=f(a)f(b)f©...\) maps every \(\varphi\in T_n\) to a unique \(\psi\in T_m\). #There are only \(|l|!\) bijections from \(l\) to itself, therefore there are only \(|l|!\) such functions \(F\) as well. #Label each such \(F\) as \(F_0,F_1...F_{ |l|!-1}\). Then, (by infinite PHP) for some \(n\), there must be infinitely many \(m\) such that \(F_n\) maps \(T_0\) to \(T_m\). However, \(F_n\) maps every formula to a unique formula, meaning it turns \(T_0\) into a unique theory, and thus a contradiction has been reached. Proof 4 Here I'll prove that H-Boogol-Boogol is larger than Rayo's number. It can be assumed that \(\mu(\text{ZFC}\) is far lower than one boogol. Then, let \(\psi\) be the 2nd-order formula in the language of \(\mathcal{L}^{<\omega}(\emptyset,\{\in\},\emptyset)\) such that \(V\models\psi(n)\) if and only if \(n\) is larger than every element of \(\omega\) definable with FOST in \(V\). It can also be assumed that \(\psi\) has less than a boogol symbols. Then, \((\text{ZFC},\psi)\) is a defining pair of Rayo's number because \(\text{ZFC}\) is verifiable (obviously). Therefore Rayo's number is (Boogol,Boogol)-representable and so H-Boogol-Boogol is larger than Rayo's number. = Possible Names = Here's a list of possible names suggested by googology wikia users: #H-Boogol-Boogol - The original name #Yeti - Suggested by Syst3ms #Many names by Emlightened: ##Harold ##Buster ##Umpteenplex ##Forearm's Constant ##Marianas Void ##Paper-Mache Constant ##MTUPKN Number ##Bruce #Randolph - Chronolegends Category:Blog posts